import java.io.Serializable;

public class YsfTest implements Serializable {


    public static void main(String[] args) {
        int index = getIndex(12,5);
        System.out.println("约瑟夫杀人游戏："+index);
    }


    /**
     * 约瑟夫杀人游戏：
     * 约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的，我们把问题描述如下：
     * - 现有T个人围成一桌坐下，编号从1到T，从编号为1的人开始报数。
     * - 报数也从1开始，报到M的人离席，从离席者的下一位在座成员开始，继续从1开始报数。
     * - 求最后一个在座的成员编号。
     * 不限于实现方式， 数组、队列、递归均可， 并估算时间复杂度。
     */
    public static int getIndex(int T,int M){
        //组成单链表，第一个节点下标为1
        Node fir=new Node(1);
        Node current=fir;
        for(int a=2;a<=T;a++){
            current.next=new Node(a);
            current= current.next;
        }
        //链表末尾next指针指向链表头部，形成循环链表
        current.next=fir;
        while(current !=current.next){
            for(int b=1;b<M;b++){
                current=current.next;
            }
            current.next=current.next.next;

        }
        return current.val;
    }


    public static class  Node{
        int val;//表示此节点的下标值
        Node next;//此节点的下一个节点
        public Node(int val) {
            this.val=val;
        }
    }

}




